#include <iostream>
#include <stdlib.h>
#include <cstddef>

struct _list_node_pointer {
	_list_node_pointer* _m_next;//指向下一个
	_list_node_pointer* _m_pre;//指向上一个
};

template <typename _T>
struct _list_node_data : public _list_node_pointer {//公有继承指针域
	_T _m_data;
};

template <typename _T>
class _list_node_base {
public:
	_list_node_data<_T>* m_head;
	_list_node_base() {
		m_head = new _list_node_data<_T>();
		m_head->_m_next = m_head;
		m_head->_m_pre = m_head;
	}
	_list_node_base(const _T& val) {
		m_head = new _list_node_data<_T>();
		m_head->_m_next = nullptr;
		m_head->_m_pre = nullptr;
		m_head->_m_data = val;
	}
	~_list_node_base() {
		m_head->_m_next = nullptr;
		m_head->_m_pre = nullptr;
		delete m_head;
	}
};

template<typename _T>
class _list_iterator {
public:
	_list_node_pointer* _m_node;
	_list_iterator():_m_node(nullptr) {}
	_list_iterator(_list_node_pointer* _x) :_m_node(_x){}
	_list_iterator& operator++();//前++
	_list_iterator& operator++(int);//后++
	_list_iterator& operator--();//前--
	_list_iterator& operator--(int);//后--
	_T operator*()const;
	_list_node_data<_T>* operator->()const;
	bool operator!=(const _list_iterator& it) const;
	bool operator==(const _list_iterator& it) const;
};
template<typename _T>
_list_iterator<_T>& _list_iterator<_T>::operator++() {
	_m_node = _m_node->_m_next;
	return *this;
}
template<typename _T>
_list_iterator<_T>& _list_iterator<_T>::operator++(int) {
	_list_iterator old = *this;
	++(*this);
	return old;
}
template<typename _T>
_list_iterator<_T>& _list_iterator<_T>::operator--() {
	_m_node = _m_node->_m_pre;
	return *this;
}
template<typename _T>
_list_iterator<_T>& _list_iterator<_T>::operator--(int) {
	_list_iterator old = *this;
	--(*this);
	return old;
}
template<typename _T>
_T _list_iterator<_T>::operator*() const{
	return ((_list_node_data<_T>*)_m_node)->_m_data;
}
template<typename _T>
_list_node_data<_T>* _list_iterator<_T>::operator->() const {
	return ((_list_node_data<_T>*)_m_node);
}
template<typename _T>
bool _list_iterator<_T>::operator!=(const _list_iterator& it) const {
	return _m_node != it._m_node;
}
template<typename _T>
bool _list_iterator<_T>::operator==(const _list_iterator& it) const {
	return _m_node == it._m_node;
}

template<typename _T>
class MyList :protected _list_node_base<_T> {
public:
	typedef _list_node_data<_T> list_node;
	typedef _list_iterator<_T> iterator;
	typedef _list_node_base<_T> _Base;
protected:
	using _Base::m_head;//结点的指针表示一个双链表
	size_t len;//结点数量
public:
	MyList() :_list_node_base<_T>(),len(0) {};//调用父类默认构造函数
	MyList(size_t _n, const _T& val = _T()) :_list_node_base<_T>(), len(0) {
		for (size_t i = 0; i < _n; i++) {
			insert(begin(), val);
		}
	}
	~MyList() {
		clear();
	}
	
	/// 清空容器
	void clear() {
		while (!empty()) {
			pop_back();
		}
	}

	/// 返回头结点的下一个
	iterator begin() {
		return (list_node*)m_head->_m_next;//最后结果为list_node*类型，将其包装为迭代器类型，通过父类指针调用子类构造函数
	}
	
	/// 返回头节点
	iterator end() {
		return (list_node*)m_head;
	}
	
	/// 获取list长度
	size_t size() const {
		return len;
	}
	
	/// 判断list是否为空
	bool empty() const {
		return len == 0;
	}
	
	/// 在pos位插入值为val的结点
	iterator insert(iterator pos, const _T& val) {
		_Base* b = new _Base(val);
		list_node* _tmp = b->m_head;
		_tmp->_m_next = pos._m_node;
		pos._m_node->_m_pre->_m_next = _tmp;
		_tmp->_m_pre = pos._m_node->_m_pre;
		pos._m_node->_m_pre = _tmp;
		++len;
		return _tmp;
	}
	/// 删除pos位的结点
	iterator erase(iterator pos) {
		if (!empty()) {
			list_node* node_next = (list_node*)pos._m_node->_m_next;
			pos._m_node->_m_pre->_m_next = pos._m_node->_m_next;
			pos._m_node->_m_next->_m_pre = pos._m_node->_m_pre;
			//清除结点
			--len;
			return (iterator)node_next;
		}
		else {
			throw "超出list长度！";
		}
	}
	/// 在begin位置插入结点
	void push_front(const _T& val = _T()) {
		insert(begin(), val);
	}
	
	/// 在end位置插入结点
	void push_back(const _T& val = _T()) {
		insert(end(), val);
	}

	/// 删除begin位置结点
	void pop_front() {
		erase(begin());
	}

	/// 删除end位置的上一个结点

	void pop_back() {
		erase(--end());
	}
};